package hot

/*
原题链接:
https://leetcode.cn/problems/maximal-square/

221. 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：
输入：matrix = [

	["1","0","1","0","0"],
	["1","0","1","1","1"],
	["1","1","1","1","1"],
	["1","0","0","1","0"]

]
输出：4

示例 2.
输入：matrix = [

	["0","1"],
	["1","0"]

]
输出：1

示例 3：
输入：matrix = [["0"]]
输出：0

思路：
使用动态规划来降低时间复杂度：
使用dp[i,j]表示以(i,j)为右下角，且只包含1的正方形的边长最大值。
如果我们能计算出所有dp[i,j]的值，那么其中的最大值即为矩阵中只包含1的正方形的边长最大值，
其平方即为最大正方形的面积
*/
func maximalSquare(matrix [][]byte) int {
	//1.声明dp数组
	dp := make([][]int, len(matrix))
	//2.声明返回值计数
	maxSide := 0

	//3.将参数数组的值拷贝到dp数组
	for i := 0; i < len(matrix); i++ {
		dp[i] = make([]int, len(matrix[i]))
		for j := 0; j < len(matrix[i]); j++ {
			dp[i][j] = int(matrix[i][j] - '0')
			if dp[i][j] == 1 {
				maxSide = 1
			}
		}
	}

	//4.按照dp递推公式计算最大边长
	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[i]); j++ {
			if dp[i][j] == 1 {
				dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1
				if dp[i][j] > maxSide {
					maxSide = dp[i][j]
				}
			}
		}
	}

	//5.返回最长边长乘积
	return maxSide * maxSide
}
